package list;


public class TailKthNode {

	public static void main(String[] args) {
		int[] a1 = { 5, 6, 9, 45, 61, 70, 75, 89 };
		ListNode head = LinkedListCreate.createList(a1);
		ListNode node = reverseList(head);
		LinkedListCreate.printList(node);
		// System.out.println(node.value);
	}

	// 反转链表
	public static ListNode reverseList(ListNode head) {

		// 如果链表为空，或者链表中的元素只有一个，返回head即可
		if (head == null || head.next == null) {
			return head;
		}
		ListNode pre = null;
		ListNode nextNode = null;
		while (head != null) {
			nextNode = head.next;
			head.next = pre;
			pre = head;
			head = nextNode;
		}
		return pre;
	}

	// 倒数第k个结点
	public ListNode FindKthToTail(ListNode head, int k) {
		if (head == null) {
			return null;
		}
		// 两个指针，一个快一个慢
		ListNode quick = head;
		ListNode slow = head;
		for (int i = 1; i < k; i++) {
			// 可能会出现k大于链表长度的情况
			if (quick != null) {
				quick = quick.next;
			} else {
				return new ListNode((Integer) null);
			}
		}
		while (quick.next != null) {
			quick = quick.next;
			slow = slow.next;
		}
		return slow;
	}
	//是否有环
	public boolean hasCycle(ListNode head) {
        if(head == null){
            return false;
        }
        ListNode fast = head, slow = head;
//        只判断fast是否为null
//        while(fast != null ){
//            slow = slow.next;
//            fast = fast.next;
//            if(fast != null){
//                fast = fast.next;
//            }else{
//                return false;
//            }
//            if(slow == fast){
//                return true;
//            }
//        }
//        return false;
        while(fast != null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                return true;
            }
        }
        //注意循环的条件是fast不为空，并且fast.next不为空
        //若只有一个头结点，并且头结点的next指向头结点，仍然应该返回true
        return head.next == head;
    }
}
